#ifndef LIBACCENT_STL_HPP
#define LIBACCENT_STL_HPP

#include "accent/core.hpp"
#include <iterator>
#include <cassert>

namespace accent
{
  namespace detail
  {
    using std::begin;

    template <typename StlRange>
    auto adl_begin(StlRange& range) -> decltype(begin(range));

    template <typename Iterator, typename Derived>
    class iterator_range_base
    {
      Iterator first, last;

    protected:
      iterator_range_base(Iterator first, Iterator last)
        : first(first), last(last)
      {}

    public:
      bool empty() const { return first == last; }

      auto front() const -> decltype(*first) {
        assert(!empty());
        return *first;
      }

      void pop_front() {
        assert(!empty());
        ++first;
      }


      class position {
        friend class iterator_range_base;

        Iterator iterator;
        bool valid;

        position(Iterator iterator) : iterator(iterator), valid(true) {}

      public:
        position() : iterator(), valid(false) {}

        explicit operator bool() const { return valid; }
        bool operator !() const { return !valid; }
        auto operator *() const -> decltype(*iterator) {
          assert(valid);
          return *iterator;
        }
        friend bool operator ==(const position& lhs, const position& rhs) {
          return (!lhs.valid && !rhs.valid) || lhs.iterator == rhs.iterator;
        }
      };

      position front_position() const {
        return empty() ? position() : position(first);
      }

      Derived from(position p) const {
        assert(p);
        return Derived(p.iterator, last);
      }

      Derived until(position p) const {
        assert(p);
        return Derived(first, p.iterator);
      }


      position back_position() const {
        if (empty())
          return position();
        auto t = last;
        --t;
        return position(t);
      }

      auto back() const -> decltype(*this->last) {
        assert(!empty());
        auto t = last;
        --t;
        return *t;
      }

      void pop_back() {
        assert(!empty());
        --last;
      }

      std::size_t size() const {
        return static_cast<std::size_t>(last - first);
      }

      void skip_front(std::size_t n) {
        assert(n <= size());
        first += n;
      }

      void skip_back(std::size_t n) {
        assert(n <= size());
        last -= n;
      }

      auto operator [](std::size_t n) const -> decltype(*this->first) {
        assert(n < size());
        return first[n];
      }
    };

    template <typename InputIterator>
    class input_iterator_range
      : private iterator_range_base<InputIterator,
                                    input_iterator_range<InputIterator>>
    {
      using base = iterator_range_base<InputIterator, input_iterator_range>;

    public:
      typedef single_pass_traversal_tag traversal;

      input_iterator_range(InputIterator first, InputIterator last)
        : base(first, last)
      {}

      using base::empty;
      using base::front;
      using base::pop_front;
    };

    template <typename ForwardIterator>
    class forward_iterator_range
      : private iterator_range_base<ForwardIterator,
                                    forward_iterator_range<ForwardIterator>>
    {
      using base = iterator_range_base<ForwardIterator, forward_iterator_range>;

    public:
      typedef forward_traversal_tag traversal;

      forward_iterator_range(ForwardIterator first, ForwardIterator last)
        : base(first, last)
      {}

      using base::empty;
      using base::front;
      using base::pop_front;

      using typename base::position;
      using base::front_position;
      using base::from;
      using base::until;
    };

    template <typename BidirectionalIterator>
    class bidirectional_iterator_range
      : private iterator_range_base<BidirectionalIterator,
                            bidirectional_iterator_range<BidirectionalIterator>>
    {
      using base = iterator_range_base<BidirectionalIterator,
                                       bidirectional_iterator_range>;
    public:
      typedef bidirectional_traversal_tag traversal;

      bidirectional_iterator_range(BidirectionalIterator first,
                                   BidirectionalIterator last)
        : base(first, last)
      {}

      using typename base::position;
      using base::empty;
      using base::front;
      using base::pop_front;
      using base::front_position;
      using base::from;
      using base::until;
      using base::back;
      using base::pop_back;
      using base::back_position;
    };

    template <typename RandomAccessIterator>
    class random_access_iterator_range
      : private iterator_range_base<RandomAccessIterator,
                             random_access_iterator_range<RandomAccessIterator>>
    {
      using base = iterator_range_base<RandomAccessIterator,
                                       random_access_iterator_range>;
    public:
      typedef random_access_traversal_tag traversal;

      random_access_iterator_range(RandomAccessIterator first,
                                   RandomAccessIterator last)
        : base(first, last)
      {}

      using typename base::position;
      using base::empty;
      using base::front;
      using base::pop_front;
      using base::front_position;
      using base::from;
      using base::until;
      using base::back;
      using base::pop_back;
      using base::back_position;
      using base::size;
      using base::skip_front;
      using base::skip_back;
      using base::operator [];
    };

    template <typename Iterator>
    class iterator_range_for
    {
      typedef typename std::iterator_traits<Iterator>::iterator_category category;

      static input_iterator_range<Iterator>
        choose_iterator_range(std::input_iterator_tag);
      static forward_iterator_range<Iterator>
        choose_iterator_range(std::forward_iterator_tag);
      static bidirectional_iterator_range<Iterator>
        choose_iterator_range(std::bidirectional_iterator_tag);
      static random_access_iterator_range<Iterator>
        choose_iterator_range(std::random_access_iterator_tag);

    public:
      typedef decltype(choose_iterator_range(category())) type;
    };
  }

  template <typename StlRange>
  auto all(StlRange& stlRange)
    -> typename detail::iterator_range_for<
         decltype(detail::adl_begin(stlRange))
       >::type
  {
    using std::begin;
    using std::end;
    return { begin(stlRange), end(stlRange) };
  }

  template <typename StlRange>
  auto all(const StlRange& stlRange)
    -> typename detail::iterator_range_for<
         decltype(detail::adl_begin(stlRange))
       >::type
  {
    using std::begin;
    using std::end;
    return { begin(stlRange), end(stlRange) };
  }
}

#endif
